﻿/*
题目：无需开会的工作日

给你一个正整数 days，表示员工可工作的总天数（从第 1 天开始）。另给你一个二维数组 meetings，长度为 n，其中 meetings[i] = [start_i, end_i] 表示第 i 次会议的开始和结束天数（包含首尾）。

返回员工可工作且没有安排会议的天数。

注意：会议时间可能会有重叠。

https://leetcode.cn/problems/count-days-without-meetings/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <array>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <algorithm>
#include <functional>
#include <random>

using namespace std;

class Solution {
public:
    /**
     * @KEY: 合并区间：根据左端点排序，不断调整右边界, 吞并有交集的区间
    */
    int countDays(int days, vector<vector<int>>& meetings) {
        // 根据开始时间排序，再根据结束时间降序
        sort(meetings.begin(), meetings.end(), [](auto& x, auto& y) {
            if (x[0] != y[0])   return x[0] < y[0];
            else                return x[1] < y[1];
            });

        // 合并所有区间，[1, 3] , [2, 6] => [1, 6]
        // 合并的过程中不断扩张右边界, 直到右边界 < 左边界，那么一段区间就合并完成了
        auto i = 0, n = static_cast<int>(meetings.size());
        while (i < n) {
            auto left = meetings[i][0], right = meetings[i][1];

            int next = i + 1;
            while (next < n && right >= meetings[next][0]) {
                if (right < meetings[next][1]) {
                    right = meetings[next][1];
                }
                next++;
            }

            days -= right - left + 1;
            i = next;
        }

        return days;
    }
};
